Ad hoc and on-demand routing is an important and critical aspect of networking, whereby network devices need not populate all of the routes and route computation is by way of on-demand requests. It is fundamentally useful as the network elements can be dynamic, mobile and simple. For example, Ad-hoc On-demand Distance Vector Version 2 (AODVv2) routing protocol is one conventional protocol designed for ad hoc mobile networks where the routes are learned by way of on-demand requests and routing tables are populated only when needed. The protocol provides a mechanism and message types to request and respond during route discovery.
In a conventional AODV model, three types of packets are used for purposes of route discovery, represented respectively as route request (RREQ), route reply (RREP), and route error (RERR). RREQ carries the message to query for a route and is broadcast over the network with a link local multicast address and with a time-to-live field value. e.g., 255. When an intermediate router receives the RREQ, it processes that message and, if it is not the owner of destination address, it rebroadcasts the RREQ. RREP is used as a reply from the destination device and is typically sent back to the source device via unicast. During a normal data plane forwarding operation, where there is no route for the packet to be forwarded to the destination, an RERR message is sent back to the source.
For instance, when a source device S needs to send data to a destination device D, S may or may not have a route for D. If the route is unknown by S for example, S can broadcast a RREQ packet with a link local multicast address. Other network devices that retransmit the request packet from S will at least temporarily maintain a route back to S. Once the RREQ packet is received at the destination, D can unicast a RREP packet, back towards S. It can be assumed that each network device receiving the RREP has received the RREQ which triggers the RREP, and so already has a route to S. Given the information included in the RREP, the receiving devices can update or create a route to D by retransmitting the RREP to the next stop along the way to S. If a device receiving the RREP (e.g., for S's discovery of a route to D) doesn't have a route for the source S, it can reply with a RERR message back to the destination D.
In a conventional ad hoc on-demand model, route maintenance is performed in order to avoid prematurely expunging routes from the routing table and causing interruption to data traffic. When an intermediate forwarding device X does not have an active link/route to forward the packet, X also needs to respond back to the source with a RERR message, so that the nodes could re-learn the routes. Receipt of RERR will typically cause the route discovery operation to be initiated by the network element which was unsuccessful in transmitting the packet triggering the RERR message.
Each network router maintains a routing table, where the router stores its route entries which may be populated by various IGP and EGP protocols for example. In fixed networks, where the network is stable and static, the routing table is traditionally huge in size, and requires the node to have a high storage capacity. To reduce size of routing tables and thus increase the mobility of the network, in a conventional AODV model, a network node only keeps active paths in its routing table. However, this leads to a large number of route requests in case of the frequent network changes and disparate traffic, e.g., frequent addition of new network nodes. The broadcast of a large number of route requests tends to aggravate network traffic, increase interference and consume more power, which are highly undesirable.